package algorithm.dynamic;

import java.util.*;

/**
 * https://leetcode.com/problems/palindrome-partitioning/
 * Medium
 *
 * 分割回文串
 * 给一个字符串，分割成子串，使得所有子串都为回文字符串
 *
 * 思路：
 * 由于要求所有的子串都必须为回文字符串。所以，我们可以使用剪枝的思路，剪掉一部分无用的分割。
 * 1、剪枝。
 *      截取以idx=0为开头的，前面的子串判断，前子串是否是回文，如果不是，则该分割直接跳过，走下一个分割
 * 2、动态规划。
 *      剪枝判断之后。该裁剪方式的所有回文子串。等于 前面子串 + 后面整个字符串的所有回文子串。
 *
 *  后面整个字符串的所有回文子串，可以使用动态规划的方式提前找出来
 *  p[i] 表示以 idx=i 为开始，往后到末尾的子串，所包含的全部回文子串的集合
 *  sub[i] 表示 以 idx=i的字符开头的子串，一直到末尾的所有回文子串的集合。
 *  递推公式：p[i] = sub[i] + p[i+1]
 *
 * Created by yzy on 2021-03-04 14:18
 */
public class PalindromePartitioning {

    // TODO 未完成
    public static void main(String[] args) {
        String str = "aba";
//        System.out.println(str.substring(0,1));
        System.out.println(str.substring(0,1));
        System.out.println(partition(str));
    }

    public static List<List<String>> partition(String s) {
        Map<Integer, List<String >> map = findAllSubPalindrome(s);
        List<List<String>> resList = new ArrayList<>();
        if(subStrIsPalindrome(s, 0, s.length()-1)){
            resList.add(Arrays.asList(s));
        }
        for(int i=1; i<s.length(); i++){
            if(subStrIsPalindrome(s, 0, i-1)){
                List<String> tmpList = map.get(i);
                tmpList.add(0,s.substring(0,i));
                resList.add(tmpList);
            }
        }
        return resList;
    }

    private static Map<Integer, List<String>> findAllSubPalindrome(String s){
        Map<Integer, List<String>> map = new HashMap<>();
        for(int i=s.length()-1; i>=1; i--){
            List<String> preList = map.get(i+1);
            if(preList == null){
                preList = new ArrayList<>();
            }
            List<String> currList = new ArrayList<>(findStartIdxSubPalindrome(s,i));
            currList.addAll(currList.size(), preList);
            map.put(i, currList);
        }

        return map;
    }

    private static List<String> findStartIdxSubPalindrome(String s, int startIdx){
        List<String> list = new ArrayList<>();
        int endIdx = startIdx;
        while(endIdx < s.length()){
            if(subStrIsPalindrome(s, startIdx, endIdx)){
                list.add(s.substring(startIdx, endIdx+1));
            }
            endIdx++;
        }
        return list;
    }

    private static boolean subStrIsPalindrome(String s, int startIdx, int endIdx){
        if(startIdx > endIdx){
            return false;
        }
        while(startIdx < endIdx){
            if(s.charAt(startIdx++) != s.charAt(endIdx--)){
                return false;
            }
        }
        return true;
    }

}
